package com.cjm.algorithm.backtracking;

import java.util.ArrayList;
import java.util.List;

public class Ti39 {
    public static void main(String[] args) {
        Ti39 ti39 = new Ti39();
        ti39.combinationSum(new int[] {2, 3, 6, 7}, 7);
        ti39.combinationSum(new int[] {2, 3, 5}, 8);
        System.err.println("OK");
    }
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        res.clear();
        method39(0, 0, candidates, target, new ArrayList<Integer>());
        return res;
    }

    private void method39(int startIndex, int currentSum, int[] candidates, int sum, List<Integer> sumList) {
        if (currentSum == sum) {
            res.add(new ArrayList<>(sumList));
            return;
        }

        for (int i = startIndex; i < candidates.length; i++) {
            int candidate = candidates[i];
            int backCurrentSum = currentSum;
            List<Integer> backList = new ArrayList<>(sumList);
            while (true) {
                backCurrentSum += candidate;
                if (backCurrentSum > sum) {
                    break;
                }
                backList.add(candidate);
                method39(i+1, backCurrentSum, candidates, sum, backList);
            }
        }

    }


}
